﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.MaxSubArray
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
            Console.WriteLine(MaxSubArray(nums));
            Console.ReadKey();
        }

        /// <summary>
        /// 动态规划
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int MaxSubArray(int[] nums)
        {
            int[] dp = new int[nums.Length];
            dp[0] = nums[0];
            int maxValue = dp[0];
            for (int i = 1; i < nums.Length; i++)
            {
                dp[i] = Math.Max(dp[i - 1], 0) + nums[i];
                maxValue = Math.Max(maxValue, dp[i]);
            }
            return maxValue;
        }
    }
}
